This application pertains to the tracking of objects, and more particularly to the tracking of a large number of objects in a computationally efficient manner.
The tracking problem is essentially one of comparing two sets of information about the objects from two different times, and determining which information in one set corresponds to that in the other. For example, a radar tracking a plurality of aircraft scans the sky over a finite time .tau., and thereafter receives returns from the objects. The reports are in the form of data vectors, each element of each vector corresponding to a piece of information about the object whence came the report. For example, such a data vector will have one element for each of the spatial coordinates of the object, and can have such other information of interest as is available, such as doppler shift, luminescence, temperature, velocity, acceleration, etc. Generally, each report vector will have d elements, consisting of at least the spatial coordinates of its corresponding object, and each track vector will have l elements, consisting of at least the spatial coordinates and velocity components of the corresponding object, 1.gtoreq.d.
With each new scan, a new set of reports are received, which must be paired with the existing tracking data vectors, called the track data structure. This pairing is done by comparing elements in the track data structure with those in the new reports at whose nodes according to a numerical scoring criterion is applied to each candidate pair. Unfortunately, the total number of these pairs is the number of data vectors in the track data structure, times the number of report vectors, this product being nominally the square of the number of objects being tracked. The computational cost of evaluating the scoring test for such a data pair is relatively high for many tracking problems of interest, such as air traffic or battle control. Moreover, the number of pairs which must be compared in the search data structure is N.sub.r N.sub.T, where N.sub.R is the number of reports, and N.sub.T is the number of tracks, a number which increases quadratically with the number of objects tracked. Thus increasing the number of objects to track can rapidly increase the computational demand beyond the limits of any computer.
To overcome this problem, prior workers typically use a very coarse, but computationally simple, criterion to prescreen the pairs of tracks and reports which have little likelihood of correspondence, and then subjecting only the pairs which "gate," i.e. survive this prescreening, the search tree and the more precise scoring test, sometimes referred to as the final gate. One way to do this is to select a radius in parameter space (the elements of the data vectors being the parameters of this space), and, for each track/report, score only those reports/tracks within the radius. Unfortunately, the finite non-zero scan time causes the reports to return at different times than they would if the scan occurred instantaneously. Because the objects have different and usually appreciable velocities, the reports are skewed in time. Thus to ensure that all legitimate pairs should pass the gate, the search radii might have to be so large as to largely offset the savings introduced by the gate. Significant attempts have been made to develop scanners having very short scan times. Unfortunately, producing such a controlled, high power, output is both difficult and expensive.